/*
 * @lc app=leetcode.cn id=93 lang=java
 *
 * [93] 复原 IP 地址
 */

// @lc code=start

import java.util.*;

class Solution {
    public List<String> restoreIpAddresses(String s) {
        if(s.length() > 12) {
            return res;
        }
        
        StringBuilder sb = new StringBuilder(s);
        backtracking(sb, 0, 0);
        return res;
    }

    List<String> res = new ArrayList<>();
    private void backtracking(StringBuilder sb, int startIndex, int pointNum) {
        if(pointNum == 3) {
            if(isValid(sb, startIndex, sb.length() - 1)) {
                res.add(sb.toString());
            }
            return;
        }

        for(int i = startIndex; i < sb.length(); i++) {
            if(isValid(sb, startIndex, i)) {
                sb.insert(i+1, '.');
                backtracking(sb, i+2, pointNum + 1);
                sb.deleteCharAt(i+1);
            }
        }
    }

    private Boolean isValid(StringBuilder sb, int start, int end) {
        if(start > end) {
            return false;
        }
        if(sb.charAt(start)  == '0' & start != end) {
            return false;
        }

        int num = 0;
        for(int i = start; i <= end; i++) {
            int digit = sb.charAt(i) - '0';
            num = num * 10 + digit;
            if(num > 255) {
                return false;
            }
        }
        return true;
    }
}
// @lc code=end

